# -*- coding: utf-8 -*-
"""
Created on Sat May 13 15:15:12 2017

@function: KNN algorithm source code
"""
from __future__ import division
import numpy as np
import operator

#创建测试数据集
def test_data():
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


#从文本中读取数据集
#功能：规定文本中每行有一个K维实例特征向量，和一个对应标签
#输入：文本文件名
#输出：从文本导入的数据集特征向量和标签
def file2mat(file_name):
    f = open(file_name)
    lines = f.readlines()
    line1 = lines[0].strip().split('\t')
    k = len(line1)-1 #特征向量的维数
    length = len(lines)
    fea_vec = np.zeros((length, k))
    label_vec = []
    i=0
    for line in lines:
        line = line.strip()
        line_list = line.split('\t')
        fea_vec[i,:] = line_list[0:k]
        label_vec.append(line_list[-1])
        i += 1
    return fea_vec, label_vec
 


#功能:归一化特征向量
#输入:数据集特征向量
#输出：原向量的 行数（即特征向量个数），列最大值向量，列最小值向量，归一化后的特征向量
def nrml(dataset):
    x_max = dataset.max(0)
    x_min = dataset.min(0)
    row = dataset.shape[0]
    x_max1 = np.tile(x_max, (row,1))
    x_min1 = np.tile(x_min, (row,1))
    dataset_nor = (dataset-x_min1)/(x_max1-x_min1)
    return x_max, x_min, dataset_nor


#功能：KNN算法实现
#输入：待预测特征向量x，数据集特征向量，数据集标签，knn的前k个最邻近
#输出：预测结果，即类别标签
def classify(x, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(x, (dataSetSize, 1)) - dataSet #a—b
    sqDiffMat = diffMat**2                             #（a-b)^2
    sqDistances = sqDiffMat.sum(axis = 1)              #平方和
    distances = sqDistances**0.53                      #开根号
    sortedDistIndicies = distances.argsort()           #argsort函数返回的是数组值从小到大的索引值
    classCount = {} #字典，对应键值对为 标签：出现次数
    for i in range(k): #选取前k个最邻近样本，判断最可能类型
        voteIlabel = labels[sortedDistIndicies[i]]    #第i个最邻近样本的标签
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #该标签出现次数加1
    sortedClassCount = sorted(classCount.iteritems(),
                              key = operator.itemgetter(1), reverse = True) #按照标签出现次数由高到低排序
    return sortedClassCount[0][0] #返回出现次数最多的标签

#功能：测试算法
#输入：训练数据集，测试数据集,KNN的前k个最邻近
#输出：错误率
def model_test(train_file, test_file, k):
    train_fea, train_lab = file2mat(train_file)
    test_fea, test_lab = file2mat(test_file)
    x_max, x_min, train_fea = nrml(train_fea) #归一化训练数据，下面是归一化测试数据
    row = test_fea.shape[0]
    x_max = np.tile(x_max, (row,1))
    x_min = np.tile(x_min, (row,1))
    test_fea = (test_fea-x_min)/(x_max-x_min)
    
    all_num = len(test_fea)
    wrong_num = 0
    for i in range(all_num):
        xtype = classify(test_fea[i], train_fea, train_lab, k)
        if xtype != test_lab[i]:
            wrong_num += 1
    wrong_rat = wrong_num/all_num
    return wrong_rat
    

#功能：主函数交互设计
def KNN_classify():
    dataset = raw_input('请输入训练数据集文件名: ')
    test_vec = input('请输入待预测特征向量: ')
    k = input('请输入KNN参数k: ')
    test_vec = np.array(test_vec)
    dataset_fea, dataset_lab = file2mat(dataset)
    x_max, x_min, dataset_fea = nrml(dataset_fea)
    test_vec = (test_vec-x_min)/(x_max-x_min)
    xtype = classify(test_vec, dataset_fea, dataset_lab, k)
    return xtype


#测试主函数
#测试程序能否正常运行
def test() :
    group, labels = test_data()
    inx = [1.2, 1.3]
    x_type = classify(inx, group, labels, 3)
    print x_type
